<html lang="en">
<head>
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">

<link type="text/css" rel="stylesheet" href="../source/css/bootstrap.css" />
<link type="text/css" rel="stylesheet" href="../source/css/bootstrap-responsive.css" />
<link type="text/css" rel="stylesheet" href="../source/css/docs.css" />
<link type="text/css" rel="stylesheet" href="../source/css/monokai.css" />
<link type="text/css" rel="stylesheet" href="../source/css/font-awesome.css">

<script type="text/javascript" src="../source/js/jquery-1.9.1.js"></script>
<script type="text/javascript" src="../source/js/bootstrap.js"></script>
<script type="text/javascript" src="../source/js/highlight.pack.js"></script>
<script type="text/x-mathjax-config"> 
    MathJax.Hub.Config({ 
        tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]} 
    }); 
</script>
<script type="text/javascript"
    src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
<title>Luogu2983</title>

</head>
<body data-spy="scroll" data-target=".bs-docs-sidebar">
<div class="navbar navbar-fixed-top">
    <div class="navbar-inner">
        <div class="container">
            <!-- .btn-navbar is used as the toggle for collapsed navbar content -->
            <a class="btn btn-navbar" data-toggle="collapse" data-target=".nav-collapse">
                <span class="icon-bar"></span>
                <span class="icon-bar"></span>
                <span class="icon-bar"></span>
            </a>

            <!-- Be sure to leave the brand out there if you want it shown -->
            <a class="brand" href="../index.html">Wahacer's blogs</a>

            <!-- Everything you want hidden at 940px or less, place within here -->
            <div class="nav-collapse collapse">
                <!-- .nav, .navbar-search, .navbar-form, etc -->
                <ul class="nav">
                    <li class="">
                        <a href="../index.html">Index</a>
                    </li>
                    
                    <li class="">
                        <a href="../Solution/index.html">Solution</a>
                    </li>
                    
                    <li class="">
                        <a href="../Algorithm/index.html">Algorithm</a>
                    </li>
                    

                </ul>
            </div>
        </div>
    </div>
</div>

<div class="container-fluid">
    <div class="row-fluid">
        <!--　侧边拦 -->
        <div class="span2 bs-docs-sidebar">
            <br><br><br>
            <div align="center"><img src="../source/picture/photo.jpg" alt="photo" width="250" height="250" /></div>
            <p align="center"><strong>Wahacer</strong></p>

        </div>

        <!-- 主内容　-->
        <div class="span8">
            <br>
            <!--Body content-->
            <h2 id="toc-0">dp</h2>
<p>自古dp出奇迹 ，是这个道理吧</p>
<p><img src="https://s1.ax1x.com/2017/10/25/UKQ9U.png" alt=""></p>
<p>Luogu2983</p>
<blockquote><p>题目描述</p>
<p>Bessie and the herd love chocolate so Farmer John is buying them some.</p>
<p>The Bovine Chocolate Store features N (1 &lt;= N &lt;= 100,000) kinds of chocolate in essentially unlimited quantities. Each type i of chocolate has price P_i (1 &lt;= P_i &lt;= 10^18) per piece and there are C_i (1 &lt;= C_i &lt;= 10^18) cows that want that type of chocolate.</p>
<p>Farmer John has a budget of B (1 &lt;= B &lt;= 10^18) that he can spend on chocolates for the cows. What is the maximum number of cows that he can satisfy? All cows only want one type of chocolate, and will be satisfied only by that type.</p>
<p>Consider an example where FJ has 50 to spend on 5 different types of chocolate. A total of eleven cows have various chocolate preferences:</p>
<p>Chocolate_Type Per_Chocolate_Cost Cows_preferring_this_type</p>
<p>1 5 3</p>
<p>2 1 1</p>
<p>3 10 4</p>
<p>4 7 2</p>
<p>5 60 1</p>
<p>Obviously, FJ can't purchase chocolate type 5, since he doesn't have enough money. Even if it cost only 50, it's a counterproductive purchase since only one cow would be satisfied.</p>
<p>Looking at the chocolates start at the less expensive ones, he can purchase 1 chocolate of type #2 for 1 x 1 leaving 50- 1=49, then purchase 3 chocolate of type #1 for 3 x 5 leaving 49-15=34, then purchase 2 chocolate of type #4 for 2 x 7 leaving 34-14=20, then purchase 2 chocolate of type #3 for 2 x 10 leaving 20-20= 0.</p>
<p>He would thus satisfy 1 + 3 + 2 + 2 = 8 cows.</p>
<p>Line 1: Two space separated integers: N and B</p>
<p>Lines 2..N+1: Line i contains two space separated integers defining chocolate type i: P_i and C_i</p>
<p>Line 1: A single integer that is the maximum number of cows that Farmer John can satisfy</p>
<p>input</p>
<p>5 50</p>
<p>5 3</p>
<p>1 1</p>
<p>10 4</p>
<p>7 2</p>
<p>60 1</p>
<p>output</p>
<p>8</p>
</blockquote>
<p>结构体排序，**贪心，我以为dp，然后GG</p>
<div class="highlight"><pre><span></span><span class="cp">#include</span><span class="cpf">&lt;cstdio&gt;</span><span class="cp"></span>
<span class="cp">#include</span><span class="cpf">&lt;cstring&gt;</span><span class="cp"></span>
<span class="cp">#include</span><span class="cpf">&lt;cmath&gt;</span><span class="cp"></span>
<span class="cp">#include</span><span class="cpf">&lt;iostream&gt;</span><span class="cp"></span>
<span class="cp">#include</span><span class="cpf">&lt;algorithm&gt;</span><span class="cp"></span>
<span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span> <span class="p">;</span>
<span class="k">template</span><span class="o">&lt;</span><span class="k">class</span> <span class="nc">T</span><span class="o">&gt;</span><span class="kt">void</span> <span class="n">read</span><span class="p">(</span><span class="n">T</span> <span class="o">&amp;</span><span class="n">x</span><span class="p">){</span>
    <span class="n">x</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="kt">int</span> <span class="n">f</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span><span class="kt">char</span> <span class="n">ch</span><span class="o">=</span><span class="n">getchar</span><span class="p">();</span>
    <span class="k">while</span><span class="p">(</span><span class="n">ch</span><span class="o">&lt;</span><span class="sc">&#39;0&#39;</span><span class="o">||</span><span class="n">ch</span><span class="o">&gt;</span><span class="sc">&#39;9&#39;</span><span class="p">){</span><span class="n">f</span><span class="o">|=</span><span class="p">(</span><span class="n">ch</span><span class="o">==</span><span class="sc">&#39;-&#39;</span><span class="p">);</span><span class="n">ch</span><span class="o">=</span><span class="n">getchar</span><span class="p">();}</span>
    <span class="k">while</span><span class="p">(</span><span class="n">ch</span><span class="o">&lt;=</span><span class="sc">&#39;9&#39;</span><span class="o">&amp;&amp;</span><span class="n">ch</span><span class="o">&gt;=</span><span class="sc">&#39;0&#39;</span><span class="p">){</span><span class="n">x</span><span class="o">=</span><span class="p">(</span><span class="n">x</span><span class="o">&lt;&lt;</span><span class="mi">1</span><span class="p">)</span><span class="o">+</span><span class="p">(</span><span class="n">x</span><span class="o">&lt;&lt;</span><span class="mi">3</span><span class="p">)</span><span class="o">+</span><span class="p">(</span><span class="n">ch</span><span class="o">^</span><span class="mi">48</span><span class="p">);</span><span class="n">ch</span><span class="o">=</span><span class="n">getchar</span><span class="p">();}</span>
    <span class="n">x</span><span class="o">=</span><span class="n">f</span><span class="o">?-</span><span class="nl">x</span><span class="p">:</span><span class="n">x</span><span class="p">;</span>
    <span class="k">return</span> <span class="p">;</span>
<span class="p">}</span>

<span class="kt">long</span> <span class="kt">long</span> <span class="n">n</span><span class="p">,</span><span class="n">b</span><span class="p">;</span>

<span class="k">struct</span> <span class="n">node</span><span class="p">{</span>
    <span class="kt">long</span> <span class="kt">long</span> <span class="n">p</span><span class="p">,</span><span class="n">n</span><span class="p">;</span>
<span class="p">}</span><span class="n">e</span><span class="p">[</span><span class="mi">100010</span><span class="p">];</span>

<span class="kt">bool</span> <span class="nf">cmp</span><span class="p">(</span><span class="n">node</span> <span class="n">a</span><span class="p">,</span><span class="n">node</span> <span class="n">b</span><span class="p">){</span><span class="k">return</span> <span class="n">a</span><span class="p">.</span><span class="n">p</span><span class="o">&lt;</span><span class="n">b</span><span class="p">.</span><span class="n">p</span><span class="p">;}</span>

<span class="kt">int</span> <span class="nf">main</span><span class="p">()</span>
<span class="p">{</span>
    <span class="n">read</span><span class="p">(</span><span class="n">n</span><span class="p">),</span><span class="n">read</span><span class="p">(</span><span class="n">b</span><span class="p">);</span>
    <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">)</span> <span class="n">read</span><span class="p">(</span><span class="n">e</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">p</span><span class="p">),</span><span class="n">read</span><span class="p">(</span><span class="n">e</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">n</span><span class="p">);</span>
    <span class="n">sort</span><span class="p">(</span><span class="n">e</span><span class="o">+</span><span class="mi">1</span><span class="p">,</span><span class="n">e</span><span class="o">+</span><span class="mi">1</span><span class="o">+</span><span class="n">n</span><span class="p">,</span><span class="n">cmp</span><span class="p">);</span>
    <span class="kt">long</span> <span class="kt">long</span> <span class="n">ans</span><span class="o">=</span><span class="mi">0</span><span class="p">;</span>
    <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span><span class="o">=</span><span class="mi">1</span><span class="p">;</span><span class="n">i</span><span class="o">&lt;=</span><span class="n">n</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span>
        <span class="kt">long</span> <span class="kt">long</span> <span class="n">k</span><span class="o">=</span><span class="n">b</span><span class="o">/</span><span class="n">e</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">p</span><span class="p">;</span>
        <span class="k">if</span><span class="p">(</span><span class="n">k</span><span class="o">&gt;</span><span class="n">e</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">n</span><span class="p">){</span>
            <span class="n">ans</span><span class="o">+=</span><span class="n">e</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">n</span><span class="p">;</span><span class="n">b</span><span class="o">-=</span><span class="n">e</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">n</span><span class="o">*</span><span class="n">e</span><span class="p">[</span><span class="n">i</span><span class="p">].</span><span class="n">p</span><span class="p">;</span>
        <span class="p">}</span>
        <span class="k">else</span> <span class="p">{</span><span class="n">ans</span><span class="o">+=</span><span class="n">k</span><span class="p">;</span><span class="k">break</span><span class="p">;}</span>
    <span class="p">}</span>
    <span class="n">printf</span><span class="p">(</span><span class="s">&quot;%lld</span><span class="se">\n</span><span class="s">&quot;</span><span class="p">,</span><span class="n">ans</span><span class="p">);</span>
    <span class="k">return</span> <span class="mi">0</span><span class="p">;</span>
<span class="p">}</span>
</pre></div>
<p>By:Wahacer</p>
<p>2017.10.25</p>
<p>23:42</p>
<p>“最想要去的地方，怎么能在半路就返航.”</p>


        </div>
  </div>
</div>
<!-- Footer
    ================================================== -->
<footer class="footer">
  <div class="container">
         Copyright (c) 2017 Powered By <a href="https://gitee.com/uncle-lu/oub">OUB</a>
         <a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/3.0/cn/"><img alt="知识共享许可协议" style="border-width:0" src="https://i.creativecommons.org/l/by-nc-sa/3.0/cn/88x31.png" /></a><br />本作品采用<a rel="license" href="http://creativecommons.org/licenses/by-nc-sa/3.0/cn/">知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议</a>进行许可。
  </div>
</footer>
<script>
    $('h1').each(function() {
        $(this).wrap('<section id="' + this.id + '"/>');
    });

    $('h1').wrap('<div class="page-header" />');
    $('h1').wrap('<div class="well well-small" />');

    $(document).ready(function() {
        var items = [];
        $('h1').each(function() {
            items.push('<li><a href="#' + this.id + '"><i class="fa fa-chevron-right pull-right"></i> ' + $(this).text() + '</a></li>');
        });  // close each()

    $('#sidebar_list').append( items.join('') );

    $('table').each(function() {
        $(this).addClass('table table-striped table-condensed table-hover');
    });

    $('.done0').each(function() {
        $(this).html('<div class="alert alert-info"><i class="fa fa-check-square-o"></i>'+$(this).html()+'</div></li>');
    });

    $('.done4').each(function() {
        $(this).html('<div class="alert alert-success"><i class="fa fa-square-o"></i>'+$(this).html()+'</div></li>');
    });
   
    $('pre').each(function() {
        $(this).html('<code>'+$(this).html()+'</code>');
    });
    hljs.initHighlightingOnLoad();
});
</script>
</body>
</html>